LeetCode 11、盛水最多的容器

一、题目描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

二、题目解析

一开始，我们先去考虑相距最远的两个柱子所能容纳水的面积。

接下来去思考，我们去移动哪根柱子会更加合适?

这里我们需要注意一点：无论移动哪根柱子，柱子之间的宽度都是变小的。

移动右边那根更高的柱子？

由于水面高度是由最短的柱子决定的，所以移动右边那根更高的柱子的时候，水面高度一定是不会增加，甚至有可能遇到更短的柱子而变小，而宽度有一定再减少，所以水的面积也一定减少。

移动左边那根更短的柱子？

这时候，水的高度是不确定的，那么面积也是不确定的，有可能比之前更大，也有可能更小或者相等。

所以，我们可以得出一个结论：移动两根柱子之间更短的那根柱子，才有可能在宽度一定变小的情况下，找到一个更高的水面，从而使得面积有可能更大。

那接下来这道题目的解法也就有了：

1、设置两个索引，分别指向容器的两侧，即索引 left 指向最左边的柱子，索引 right 指向最右边的柱子。

2、记录下此时的水的面积，可以定义为 res

3、观察需要向内移动哪根柱子

• 1）如果移动较高的柱子，由于水的宽度在变小，而水的高度一定不会增加，所以最终水的面积不会超过之前记录的水的面积 res
• 2）所以，只能移动较短的柱子，然后计算此时水的面积，再与之前记录的水的面积 res 进行比较，保存那个更大的值

4、再去判断应该向内移动哪根柱子

5、直到 left 和 right 相遇为止

三、参考代码

class Solution {
    public int maxArea(int[] height) {
       
       // 设置两个索引，分别指向容器的两侧

       // 索引 left 指向最左边的柱子
       int left = 0;

       // 索引 right 指向最右边的柱子
       int right = height.length - 1;

       // 设置一个变量用来保存当下水的最大面积
       int res = 0;

       // 移动 left 和 right，直到 left 和 right 相遇为止
       while(left < right){

           // 水的宽度是 right - left
           int width = right - left;

           // 水的高度由两根柱子最短的那根决定
           int h = Math.min(height[left],height[right]);

           // 计算此时水的面积
           int area = width * h;

           // 如果此时水的面积大于了我们之前保存的那个值，我们需要更新一下
           if(area >= res){
               // 更新 res 的值为 area，确保 res 一直都是最大的值
               res = area;
           }
        
           // 接下来去观察需要移动哪根柱子：必定是最短的那根柱子

           // 如果左边的柱子更短，那么向内移动左边的柱子，因为只有这样，才有可能找到一个更高的水面
           // 在宽度一定变小的情况下，水的面积才有可能增大
           if(height[left] < height[right]){
               // 向内移动左边的柱子
               left++;

           // 如果右边的柱子更短，那么向内移动右边的柱子，因为只有这样，才有可能找到一个更高的水面
           // 在宽度一定变小的情况下，水的面积才有可能增大
           }else{
               // 向内移动右边的柱子
               right--;
           }

       }
       
       // 最后返回最大的面积 res 即可
       return res;
    }
}
# https://www.algomooc.com/587.html
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 盛最多水的容器 ( LeetCode 11) : https://leetcode-cn.com/problems/container-with-most-water/
class Solution:
    def maxArea(self, height: List[int]) -> int:
       # 设置两个索引，分别指向容器的两侧

       # 索引 left 指向最左边的柱子
       left = 0

       # 索引 right 指向最右边的柱子
       right = len(height) - 1

       # 设置一个变量用来保存当下水的最大面积
       res = 0

       # 移动 left 和 right，直到 left 和 right 相遇为止
       while left < right :

           # 水的宽度是 right - left
           width = right - left

           # 水的高度由两根柱子最短的那根决定
           h = min(height[left],height[right])

           # 计算此时水的面积
           area = width * h

           # 如果此时水的面积大于了我们之前保存的那个值，我们需要更新一下
           if area >= res :
               # 更新 res 的值为 area，确保 res 一直都是最大的值
               res = area
           
           # 接下来去观察需要移动哪根柱子：必定是最短的那根柱子

           # 如果左边的柱子更短，那么向内移动左边的柱子，因为只有这样，才有可能找到一个更高的水面
           # 在宽度一定变小的情况下，水的面积才有可能增大
           if height[left] < height[right] :
               # 向内移动左边的柱子
               left += 1

           # 如果右边的柱子更短，那么向内移动右边的柱子，因为只有这样，才有可能找到一个更高的水面
           # 在宽度一定变小的情况下，水的面积才有可能增大
           else:
               # 向内移动右边的柱子
               right -= 1
            
       # 最后返回最大的面积 res 即可
       return res